The present invention relates to computer graphics systems, and more specifically, to computer graphics systems that render primitives utilizing at least one frame buffer and depth buffer.
Rendering of three-dimensional scenes requires a realistic representation of multiple objects in the field of view. Depending on the distance of each object from a given point of view (also known in 3D graphics as camera position), objects may occlude or be occluded by other objects. Even in the case of a single object, some of its parts may occlude or be occluded by other parts. Methods and apparatus used to resolve occlusions and eliminate hidden surfaces play an important role in creating realistic images of three-dimensional scenes.
To work effectively, methods of eliminating hidden surfaces have to utilize a depth resolution that is better than the minimal distance between the occluding object and the occluded object in the scene. Such methods also have to be simple enough to be implemented in low-cost graphics hardware that accelerates three-dimensional rendering, or in software-only rendering in cases where a hardware accelerator is not available.
Most popular algorithms for hidden surface elimination utilize depth buffers, or Z-buffers. Typically, a pixel represented on a screen at a two-dimensional location X,Y is also associated with a particular depth value, Z. This value is usually compared with a depth value stored in a special buffer at the location corresponding to the same X,Y coordinate set. Visibility tests compare new and stored depth values. If these tests pass, the depth value in the depth buffer can be updated accordingly.
Values of X,Y,Z are generally computed per each vertex of a triangle by transforming three-dimensional vertex coordinates from the view space (regular three-dimensional space with the origin of the coordinates aligned with the camera position) to the screen space (a three-dimensional space with the X,Y plane being parallel to the screen and distorted as a result of perspective projection). During this transformation the actual depth of the object in the camera field of view (Zv) is mapped to the depth (Zs) in the screen space. After values of Zs are computed for every vertex of the triangle they are linearly interpolated for every pixel during triangle rasterization. Interpolation results are compared with Zs values stored in the Z-buffer at corresponding locations to test visibility of the current pixel.
The most popular form of mapping between Zv and Zs, which is supported by practically all hardware graphics accelerators, is known as xe2x80x9cscreen Z-bufferxe2x80x9d and is described in detail by W. M. Newman and R. F. Sproull in Principles of Interactive Computer Graphics, published by McGraw-Hill in 1981 and incorporated herein by reference. Newman and Sproull describe the following definition for mapping between Zv and Zs as follows:       Z    s    =                    Z        f                              Z          f                -                  Z          n                      *          (              1        -                              Z            n                                Z            v                              )      
where Zf and Zd are distances from the camera to the far (Zf) and near (Zn) clipping planes that bound the view volume in the screen space.
Non-linear mapping between Zv and Zs makes Zs less sensitive to changes in Zv that occur close to the far end of the view volume than to changes in Zv that occur close to the near end of the view volume. For example, in an instance where the ratio of distances to the far and near planes is equal to 100, a small change in Zv close to the near plane causes a larger change in Zs, for example, by a factor of 10,000 or so, than the same amount of change in Zv close to the far plane. For example, a flight simulator application may have a range of visual distances from 0.1 mile for the closest point on the group or a plane in the same formation to a 1-mile distance to the mountains near the horizon. If the total resolution of the depth buffer is 16 bits (the Zs range from 0 to 65,325 (216)), changing Zs from zero to one (i.e., close to the camera) corresponds to changing the object""s distance by 0.95 inches, while changing Zs from 65,324 to 65,325 (i.e., far from the camera) corresponds to changing the object""s distance by 797 feet. If the total resolution of the depth buffer is 24 bits, changes in the object""s distance close and far from the camera are decreased by a factor of 256. However, increasing the depth buffer from 16 to 24 bits increases memory bandwidth required for depth buffer access.
The bandwidth required to access external buffers that store color and depth values is a scarce resource, limiting the performance of modern 3D graphics accelerators. Usually, bandwidth consumed by a depth buffer is significantly larger than that consumed by the color buffer. For instance, if 50% of the pixels are rejected after a visibility test, the depth buffer may need three times more bandwidth than the color buffer. The depth values are read for all the pixels, and are written for 50% of the pixels, while the color values are only written for 50% of the pixels.
Several conventional approaches have been developed to reduce limits controlling the balance between the resolution of the depth buffer (i.e., 16-bit/24-bit) and rendering performance. In one approach, the mapping between the distance from the camera Zv and the stored depth values is modified to increase effective depth resolution. The use of a different mapping equation than that described above can be accompanied by the use of a different storage format. For example, a depth buffer having increased resolution (for example, a 1/W buffer) is described in U.S. Pat. No. 6,046,746, entitled xe2x80x9cMethod and Apparatus Implementing High Resolution Rendition of Z-buffered Primitivesxe2x80x9d, and is incorporated herein by reference. Such a depth buffer stores values proportional to 1/Zv in the floating-point format. Another type of depth buffer (a complementary Z-buffer) is described in a paper written by E. Lapidous and G. Jiao, entitled xe2x80x9cQuasi Linear Z-bufferxe2x80x9d, published in 1999 in the Proceedings on the Conference of SIGGRAPH 99, and incorporated herein by reference. The complementary Z-buffer further increases depth buffer resolution for objects positioned far from the camera by storing values equivalent to 1xe2x88x92Zs in floating-point format. Yet another type of depth buffer (a W-buffer) is used by Microsoft Corporation as a reference for measuring quality of 3D graphics accelerators, and stores values proportional to Zv providing a constant depth precision across the view volume.
The utility of these depth buffers in 3D software applications is limited in that such depth buffers are optional components and may not be supported by the widely available graphics hardware. Developers desiring maximum exposure of their product(s) typically design 3D applications so that they can be rendered correctly using a de-facto standard supported by almost all 3D graphics accelerators, which to date is a 24-bit screen Z-buffer conforming with equation (1) above. Even if a different type of depth buffer is supported by a particular 3D hardware accelerator, the lack of applications that exploit improved precision limit the usefulness of this feature. Further, the use of the W-buffer as a reference also limits development of depth buffers having increased precision, since depth buffers with an increased precision compared with the W-buffer may produce a different image, and be treated as an error by the quality control software. Thus, 3D applications are designed to correctly render images using either the 24-bit W-buffer or the 24-bit screen Z-buffer, limiting the minimally required depth precision in each point of view volume to the least of the two precision values available at that point.
In another approach, data exchange used during access to the depth buffer is modified to decrease the required bandwidth. For instance, U.S. Pat. No. 5,844,571, entitled xe2x80x9cZ-buffer Bandwidth Reductions Via Split Transactionsxe2x80x9d, which is incorporated herein by reference, describes Z-buffer bandwidth reductions via split transactions, where the least significant bits of a value in the depth buffer are read only if reading the most significant bits of the value is not enough to resolve visibility. This solution decreases the bandwidth required to read depth values, however, the bandwidth required to write depth values for pixels that pass visibility tests remains unchanged. If the latency associated with reading the depth values is large, multiple accesses to a stored depth value during a visibility test on the same pixel may decrease performance even during read operations, or require expensive measures to compensate doubled access latency. This problem is exacerbated by the fact that the request to read the least significant bits of a depth value can be issued only after a new depth value is computed and compared with the old most significant bits of the depth value. The next read request for the same pixel is delayed by a combination of the latency of the first read and of the time required to compute a new depth value.
The present invention provides a system and method for eliminating hidden surfaces in 3D graphics that improves rendering performance by decreasing the size of the data stored to or retrieved from the depth buffer when the distance from the camera to the pixel on the surface of a primitive is further than a threshold distance. The threshold distance from the camera is defined such that for such pixels the precision of a linear or quasi-linear depth buffer with a decreased data size is the same as or higher than the precision of a non-linear depth buffer with an original data size. The invention also improves the usefulness of linear and quasi-linear depth buffers for 3D applications that are optimized for non-linear depth buffers. The present invention also affords a method for selecting the size of the data to be read from the depth buffer before new depth values are computed for the same pixels.
In an aspect, the invention affords a method for identifying whether a given primitive is visible by a camera in a view volume at a pixel P corresponding to an area on the surface of a given primitive. The method comprises the steps of: storing a first depth value that is associated with the pixel P in a buffer, the first depth value including a first portion including the most significant bits of the first depth value and a second portion including the least significant bits of the first depth value; computing a second depth value that is associated with the pixel P, the second depth value including a third portion including the most significant bits of the second depth value and a fourth portion including the least significant bits of the second depth value; comparing the second depth value with a value corresponding to the threshold distance from the camera; retrieving at least the most significant bits of the first depth value; comparing the retrieved bits with the second depth value to determine if the pixel P is visible; and if the pixel P is visible and is closer to the camera than the threshold distance, replacing the first depth value with the second depth value; if the pixel P is visible and is further from the camera than the threshold distance, replacing the first portion of the first depth value with the third portion of the second depth value while leaving the second portion of the first depth value unchanged.
If the pixel P is closer to the camera than the threshold distance, the step of retrieving includes retrieving the first and second portions of the first depth value, and if the pixel P is further from the camera than the threshold distance, the step of retrieving includes retrieving only the first portion of the first depth value. If the pixel P is closer to the camera than the threshold distance, the second portion of the first depth value is retrieved before comparing the retrieved bits with the second depth value.
The second depth value is computed in accordance with a function of the distance from a camera Zv and the second depth value is stored in accordance with a predefined storage format. The threshold distance from the camera Zt is at a distance to a plane in the view volume located between near and far planes at corresponding distances Zn and Zf. For a pixel P further from the camera than the threshold distance, the error in defining Zv while using the third portion of the second depth value is equal to or less than the error in defining Zv while using the third and fourth portions of the second depth value if the second depth value is computed using the function Z=Zf/(Zfxe2x88x92Zn)*(1xe2x88x92Zn/Zv). The second depth value is scaled by a bit size corresponding to a maximum bit size that can be stored in the buffer. The second depth value is preferably stored in the buffer in an integer format.
The predefined storage format is preferably a floating-point format including an exponent and a mantissa, where the first portion of the second depth value includes the exponent and a fifth portion corresponding to the most significant bits of the mantissa, and where the second portion of the second depth value includes a sixth portion corresponding to the least significant bits of the mantissa.
For a pixel P further from the camera than a threshold distance, the error in defining Zv at any distance of the view volume using the third and fourth portions of the second depth value is less than or equal to the maximum of the error in defining Zv using the third and fourth portions of the second depth value calculated in accordance with either the function Z=Zf/(Zfxe2x88x92Zn)*(1xe2x88x92Zn/Zv) or the function Z=Zv/Zf.
In another aspect, the invention affords an alternative method for identifying whether a given primitive is visible by a camera in a view volume at a pixel P corresponding to an area on the surface of a given primitive. The method comprises the steps of: storing a first depth value that is associated with the pixel P in a buffer, the first depth value including a first portion including the most significant bits of the first depth value and a second portion including the least significant bits of the first depth value; retrieving a first set of bits corresponding to the first portion of the first depth value; comparing the retrieved first set of bits with a value corresponding to a threshold distance from the camera; computing a second depth value that is associated with the pixel P, the second depth value including a third portion including the most significant bits of the second depth value and a fourth portion including the least significant bits of the second depth value; and if the retrieved first set of bits correspond to a distance to the camera closer than the threshold distance, retrieving a second set of bits corresponding to the second portion of the first depth value and comparing the second depth value with the first depth value to determine if the pixel P is visible; if the retrieved first set of bits correspond to a distance to the camera that is further than the threshold distance, comparing the second depth value with the first portion of the first depth value to determine if the pixel P is visible; and if the pixel P is visible, replacing the first depth value with the second depth value in the buffer.
If the first set of retrieved bits correspond to a distance to the camera that is closer than the threshold distance, the step of replacing the first depth value with the second depth value includes replacing the first depth value with the second depth value. If the first set of retrieved bits correspond to a distance to the camera that is further than the threshold distance, the step of replacing the first depth value with the second depth value includes replacing only the first portion of the first depth value with the third portion of the second depth value. The second depth value is computed in accordance with a function of the distance from a camera Zv and is stored in accordance with a predefined storage format, where the threshold distance from the camera Zt is a distance to a plane in the view volume that is located between near and far planes at corresponding distances Zn and Zf.
For a pixel P that is further from the camera than a threshold distance, the error in defining Zv while using the third portion of the second depth value is equal to or less than the error in defining Zv while using the third and fourth portions of the second depth value if the second depth value is computed using the function Z=Zf/(Zfxe2x88x92Zn)*(1xe2x88x92Zn/Zv). The function is a linear dependency between the second depth value and the distance to the camera. Preferably, the second depth value is stored in the buffer in an integer format.
The predefined storage format is preferably a floating-point format including an exponent and a mantissa, and wherein the first portion of the second depth value includes the exponent and a fifth portion corresponding to the most significant bits of the mantissa, and wherein the second portion of the second depth value includes a sixth portion corresponding to the least significant bits of the mantissa.
In another aspect, the invention provides an apparatus for evaluating the depth of a pixel P in a scene, the scene being enclosed in a view volume defined by a near and a far plane, and rendered from a camera position. The apparatus comprises a depth value calculation module configured to calculate a depth value for a pixel in the scene, the depth value being generated in accordance with a depth function of view distance within the view volume from the camera position, a depth storage module configured to store the depth value in a depth value storage buffer, the depth value having a first portion corresponding to the most significant bits of the depth value and a second portion corresponding to the least significant bits of the depth value, a comparator that compares the calculated depth value with a value corresponding to a threshold distance from the camera, a visibility testing module that compares the calculated depth value with a depth value fetched from the depth buffer to determine if the pixel P is visible, and a decision logic module that, based on the comparison performed by the first comparator, causes the depth storage module to perform one of the functions of: storing the calculated depth value in the buffer if the pixel P is closer to the camera than the threshold distance, or storing only the first portion of the calculated depth value in the buffer if the pixel P is further from the camera than the threshold distance.
The decision logic module causes the depth storage module to perform one of the additional functions: fetching the depth value from the depth buffer prior to sending it to the visibility testing module if the pixel P is closer to the camera than the threshold distance, or fetching only the first portion of the depth value from the depth buffer prior to sending it to the visibility testing module if the pixel P is further from the camera than the threshold distance.
The threshold distance from the camera Zt is a distance to a plane in the view volume that is located between near and far planes at corresponding distances Zn and Zf, and for any pixel P that is further from the camera than the threshold distance, the error in defining Zv while using the first portion of the depth value computed using the depth value calculation module and stored using a storage format of the depth storage module is equal to or less than the error in defining Zv while using the first and second portions of the depth value if the depth value is computed using the function Z=Zf/(Zfxe2x88x92Zn)*(1xe2x88x92Zn/Zv). The depth storage module is configured to store depth values in an integer format, and the depth evaluation module utilizes a depth function in accordance with a linear dependency between a stored depth value and the distance to the camera.
The predefined storage format is preferably a floating-point format including an exponent and a mantissa, and wherein the first portion of the depth value includes the exponent and a third portion corresponding to the most significant bits of the mantissa, and wherein the second portion of the depth value includes a fourth portion corresponding to the least significant bits of the mantissa. The size of the first portion of the depth value is preferably 16 bits, and the size of the second portion of the depth value is preferably 8 bits. The comparator is configured to compare the calculated depth value with the value corresponding to the threshold distance to the camera only if the ratio of the distances to the far and near planes Zf/Zn is larger than a predetermined value that is preferably greater than or equal to 100.